//
//  Dijkstra.cpp
//

#include "Dijkstra.h"

Dijkstra::Dijkstra(Graph* graph, int k) {
    this->graph = graph;
    this->k = k;
    
    initializeNodes(); // O(k * n^2)
}

void Dijkstra::findPath(Node* fromNode, Node* toNode) {
    // seteo el fromNode, para que se no se salte a el
    fromNode->maxKLeftSoFar = k;
    fromNode->minJumps = 0;
    unvisited.push(new UnvisitedNode(fromNode, 0, k)); // O(1), porque la queue estaba vacia
    
    unsigned long unvisitedMaxLength = 0;
    while (unvisited.size() > 0) { // O(k * n^2), porque |unvisited| <= k * n^2
        if(unvisited.size() > unvisitedMaxLength) {
            unvisitedMaxLength = unvisited.size();
        }
        UnvisitedNode* unvisitedNode = unvisited.top(); // O(1)
                       
        Node* node = unvisitedNode->node;
        int jumpsSoFar = unvisitedNode->jumpsSoFar;
        int kLeft = unvisitedNode->kLeft;
        
        delete unvisitedNode;
        
        unvisited.pop(); // O(log(n^2)) = O(log(n))
        
        if (node == toNode) {
            break;
        }
        
        // Chequeo todos los nodos a los que puedo ir. Si hay nodos a los que puedo ir con menor
        // cantidad de saltos que los que haya usado para llegar a ese nodo hasta ahora, entonces
        // a ese nodo le seteo que el nodo anterior es el actual y con que cantidad de saltos y kLeft llegue.
        // En cambio si hay nodos a los que ya llegue con menos saltos pero menos kLeft, entonces
        // tambien almaceno en esos nodos el kLeft con el que llego
        // En ambos casos pongo los nodos como no visitados, estableciendo el rango de kLeft con el que los visite. En el primer caso el rango va a ser [0, kLeft] y en el segundo va a ser [prevMaxKLeft+1, kLeft], donde prevMaxKLeft es el kLeft maximo con el que habia llegado
        for (int i=0; i<node->edgesToNextNodes.size(); i++) { // O(2*(n-1)) = O(n)
            Arrow* edgeToNextNode = node->edgesToNextNodes[i];
            Node* nextNode = edgeToNextNode->toNode;
            int kUsed = edgeToNextNode->kUsed;
            int powerUsed = edgeToNextNode->powerUsed;
            int nextNodeKLeft = kLeft - kUsed;
            if(jumpsSoFar + 1 < nextNode->minJumps && nextNodeKLeft >= 0) {
                // como siempre saco los nodos por la minima cantidad de saltos, solo va a pasar
                // una vez que la minima cantidad de saltos + 1 sea menor a la del nodo siguiente
                nextNode->minJumps = jumpsSoFar + 1;
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = nextNode->minJumps;
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, nextNodeKLeft)); // O(log(|unvisited|))
            } else if(nextNode->maxKLeftSoFar < nextNodeKLeft && nextNodeKLeft >= 0) {
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = jumpsSoFar + 1;                
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, nextNodeKLeft)); // O(log(|unvisited|))
            }
        }
    }
}

void Dijkstra::initializeNodes() { // O(k * n^2)
    for (int i=0; i<graph->nodes.size(); i++) { // O(n^2)
        Node* node = graph->nodes[i];
        node->jumpsSoFar.resize(k+1); // O(k)
        node->prevNodes.resize(k+1); // O(k)
        for (int ikLeft=0; ikLeft<=k; ikLeft++) { // O(k)
            node->jumpsSoFar[ikLeft] = INT32_MAX; // O(1)
            node->minJumps = INT32_MAX;
            node->prevNodes[ikLeft] = new Arrow(node, 0, k);
        }
    }
}